package leetcode;

import java.util.Stack;

public class Leetcode143 {
    public void reorderList(ListNode head) {
        if(head==null){
            return;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode l2 = slow.next;
        slow.next=null;
        ListNode l1 = head;

        l2 = reverse(l2);
        merge(l1,l2);

    }

    public ListNode reverse(ListNode head){
        ListNode newNode = null;
        while(head!=null){
            ListNode next = head.next;
            head.next = newNode;
            newNode = head;
            head = next;
        }
        return newNode;
    }

    public void merge(ListNode l1,ListNode l2){
        while(l1!=null&&l2!=null){
            ListNode next1 = l1.next;
            ListNode next2 = l2.next;
            l2.next = next1;
            l1.next = l2;
            l1 = next1;
            l2 = next2;
        }

    }
}
